1. Technical Field
This invention relates generally to the field of computer networks, and particularly to quality of service management of data transmitted over a computer network.
2. Background of the Art
Currently, one of the fastest growing markets is the network services provider market, such as wide area network (“WAN”) backbones and Internet core switch services, in which bandwidth needs are exploding. For network services providers to differentiate themselves from each other, value-added services, such as quality voice capability over a network, is a desirable service to offer. However, with such value-added services, even greater amount of bandwidth as well as a greater control over the network is needed.
Currently, network service providers rely upon conventional switches to connect dial-in port concentrators to the backbone of the network, such as the Internet, as well as to network computer servers. These servers and port concentrators typically communicate with each other through the use of the Internet protocol (“IP”). The port concentrators typically communicate with the backbone of the network through the use of the asynchronous transfer mode (“ATM”) protocol. Due to the high bandwidth associated with ATM, ATM switches typically are the preferred type of switches for the network service provider's core network. In particular, this high bandwidth is due to the use in ATM of fast explicit rate (“ER”) flow control, hard quality of service (“QoS”), good QoS routing and virtual circuit (“VC”) switching. However, there are certain limitations that exist with ATM that discourage the future use of this protocol within higher capacity switches.
The primary problems with ATM switches are the fixed sizes of ATM cells, too many operating system interrupts that reduce peak speed, costly network interface card, a 20% “cell tax” overhead, signaling too slow for data (e.g., due to round trip path set-up and closure) and poor routing stability. For example, in ATM, VC technology typically is used to achieve bandwidth that is needed for voice and video data. In addition, VC technology is able to achieve better flow control and quality of service (“QoS”) for data than a conventional IP-based system. The VC concept, which was developed by Dr. Lawrence Roberts for X.25, establishes a simple marked path through the network that not only greatly increases switching speed, but also creates a context for the QoS and flow control for each call transmission. Without VC-based ATM in a conventional system, it is nearly impossible to provide “hard QoS” or controlled delay variation that is required for toll quality two-way voice and video.
ER flow control is needed in ATM to stop the delay creep associated with world wide web access. However, ER flow control only is beneficial for switches that also have VC switching. Switches along a VC path, which are supporting ER flow control, mark small out of band packets to indicate the maximum rate that can be for sending data. The ATM switch needs the VC context to identify VC's and to mark the path back to the source. Fast signaled VC ATM-based switching can accomplish this transmission rate and still operate 20 times faster than a conventional IP packet switch. However, ER flow control is very difficult to design and to support the many to one joints in the VC mesh-type structure. This configuration typically requires approximately 100 times the processing time per packet that normal packet processing requires. Such requirements are infeasible with today's conventional high speed switches. Furthermore, the scalability of the VC ATM-based switch is limited by the number of VC's available in ATM. In particular, this characteristic limits the number of destinations ATM can set up. As the Internet grows, this limitation will create a serious limitation for ATM. Furthermore, without the capability to join together on a certain trunk VC's that are going toward the same destination, the size of a conventional network that can be supported is further severely limited. In addition, with regard to failure recovery, when a trunk or switch fails within a VC mesh, the routes must be rebuilt. If there are pre-formed alternate paths, the alternate routes also must be rebuilt. The time to rebuild depends upon the call setup rate of the switch technology and if that is not much faster than ATM call setup is today, the rebuild time can become excessive and intolerable in conventional networks. In addition, if the network 100 utilizes the synchronous optical network (“SONET”) protocol, failure of a trunk line results in the need for all traffic to be redirected from that trunk, which typically results in a 50 millisecond outage.
Because of protocol complexity and because of the reliance upon software-implemented protocols for ATM switches, the signaling protocol is too slow and the virtual circuit (“VC”) allocation is too low for conventional ATM switches to provide the necessary capacity for next generation services. In addition, with world wide web applications permeating all across the Internet and Intranets, the signaling rates and VC counts are becoming far too high for current conventional ATM switches to be useful. Thus, even though ATM's protocol stack is currently viewed as superior to other protocol stacks, such as IP, ATM is becoming limited because it cannot compete with IP in cost to the user and in signaling capacity on the network backbone for the network service provider.
To attempt to offer the robustness of ATM, but through the use of IP, alternative conventional protocols for IP have been proposed for offering a certain quality of service (“QoS”). In particular, the specific advantages associated with transmission control protocol (“TCP”)/IP include the ability to have variable size packets, less operating systems interrupts, cheaper NICs, fast routing for data calls and packets can be efficiently transmitted over a trunk.
However, conventional networks 100 utilizing TCP/IP as illustrated in FIG. 9 are very slow due to TCP flow control, the lack of availability of standard or hard QoS, the lack of Qos routing and the limitations associated with analyzing each packet for routing purposes. In particular, since conventional networks 100 cannot route information based upon per-flow state information, conventional networks 100 are unable to route each flow on a path with sufficient capacity. Rather, as illustrated in FIG. 1A, a conventional network 100 focuses upon total capacity available and not on the availability of guaranteed rate (“GR”) capacity. In particular, a conventional network 100 selects the shortest path for a group of micro-flows (“composite flow”) and transmits that composite flow entirely over that designated path. This technique typically leads to the overloading of a specific trunk line, thereby making QoS very difficult to implement. Without state information, a switch cannot identify which path each micro-flow should be sent over. This limitation prevents the switch from splitting the composite flow into smaller micro-flows that can be routed over specific routes that have available capacity.
Without the ability to avoid having to rely upon composite flows, the network 100 is unable to route these micro-flows in the most efficient manner over the network 100. For example, if a trunk line on the network 100 was not able to manage the additional capacity associated with a composite flow (e.g., composite flow (A+B)), that composite flow would have to be rerouted onto another trunk line. Because the composite flow could not be resized, composite flow (A+B) could only be rerouted onto a trunk with at least the capacity needed for this composite flow. Any trunk lines that have less than the capacity needed for composite flow (A+B) would remain unused.
If all paths within a network 100 were fully loaded, conventional networks 100 also cannot discard packets from a specific micro-flow, thereby limiting the efficiency of the network 100. Discarding correctly is an important component for achieving efficient QoS for data transmissions. Internet users (e.g., users of user datagram protocol (“UDP”) and TCP) will send information as fast as possible since there is no traffic control except for packet loss. These applications, therefore, quickly can fill all of the buffers on a conventional network 100. As illustrated in FIG. 9, random early discards (“RED”), which are proportional to the buffer fill, can save the switch from becoming overloaded, but unfortunately results in wreaking havoc on the QoS of the transmission. Without the capability of intelligent discarding, true QoS cannot be achieved.
For example, for TCP, a conventional network 100 cannot avoid discarding before the user is up to the available rate. For UDP, a conventional system cannot discard even though the stream is at an acceptable rate. Without state information per micro-flow, the network 100 cannot determine the rate of each flow and thus optimize the discards. Without state information, if a source (e.g., computer system 110B) is misbehaving by sending data too fast, a conventional network 100 also cannot discard a packet associating with these data transmissions to ensure buffer space is available for those sources (e.g., computer system 110A) that are behaving. Therefore, the switch cannot punish the misbehaving source, which thereby results in all flows suffering degradation as a result of the misbehaving source.
Several conventional protocols have been proposed to attempt to address these limitations with regard to achieving QoS in an IP network. Resource reservation protocol (“RSVP”), which is described within the Internet Engineering Task Force (“IETF”)'s Request for Comments (“RFC”) for “Resource ReSerVation Protocol (RSVP)—Version 1 Functional Specification” (“RFC 2205”) and “Specification of Guaranteed Quality of Service” (“RFC 2212”) was intended to allow a flow to signal its requirements. However, the complexity and processing time involved with RSVP negotiation makes RSVP as poor as ATM for flow setup.
Differentiated Services (“DiffServ”) is an alternative technique to RSVP, which utilizes 6 Diffserv bits in the IP header to indicate one of several limited QoS classes. In particular, as discussed in the IETF's “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers” (“RFC 2474”) and “An Architecture for Differentiated Services” (“RFC 2475”), DiffServ is intended to allow network service providers to offer to each network user a range of network services which are differentiated on the basis of performance. In such a scheme, by marking a specific field (e.g. the DS field) of each packet with a specific value, a user can request on a packet by packet basis a specific limited performance class level. This value would specify the per-hop behavior to be allotted to that packet within the provider's network.
Typically, the user and network provider would negotiate a profile (e.g. policing profile) that describes the rate at which traffic can be submitted at each service class level. Packets submitted in excess of this profile would not be allotted the service class level requested. An important feature of DiffServ is viewed to be its scalability, which allows the protocol to be deployed in very large networks. This scalability is achieved by forcing as much complexity out of the core of the network and into the boundary devices that process lower volumes of traffic and lesser numbers of flows.
However, this protocol has significant limits that preclude DiffServ from providing an effective solution to the problems faced with implementing QoS in an IP network. For example, DiffServ is a traffic classification technique that only has 6 bits with a total of only 13 general service classes defined. Four classes are reserved for assured service. One class is reserved for expedited service. There, however, are no QoS definitions to quantify each class, which thereby limits the QoS types that can be supported. Since the Internet will need to be able to carry a wide variety of QoS types, this quantification limitation greatly restricts the future use of DiffServ-based QoS in large networks. By oversimplifying the QoS characterization problem by relying upon simple non-quantified classes, the overall effectiveness of such QoS in IP has been minimized.
DiffServ in the IP context also does not allow each packet to be routed with state information associated with each packet. Only one route is allowed by the border gateway protocol (“BGP”) and the routing protocols. As illustrated in FIG. 1B, DiffServ allows micro-flows to be grouped by DiffServ classes and routed together as part of a composite flow. However, such composite flows may far exceed the routing path's capacity. In addition, without state information, multiple routes cannot be used because of packet ordering problems. With no state information and only DiffServ bits, the best that a conventional switch can do is to set up multiple queues, each receiving all of the packets of a specific QoS class. Within such a queue, there would be no way to avoid head-of-line blocking. Since the queues do not correspond to single micro-flows, weighted fair queuing (“WFQ”) cannot achieve an improvement in such factors as delay variation. Instead, WFQ in this context would result in further delaying traffic. Priority queuing, which allows low delay variance traffic to be transmitted first and high delay variance traffic to be transmitted later, is the best that can be done without using state information. However, if one source (e.g., computer system 110C) is transmitting at a much higher rate, this scheme causes major problems with regard to the ability to route the higher delay variance traffic. Without keeping per micro-flow state information, WFQ techniques cannot minimize delay variation and cannot provide correction to the agreed rate at each switch. Thus, delay variance cannot be kept constant and cannot be prevented from cumulating across the network. In such a conventional network 100, delay variation, therefore, would not be able to be made extremely small, which is needed characteristic for voice interconnecting to an analog phone or for moving pictures expert group—extension 2 (“MPEG-2”) video.
The IETF has proposed an alternative conventional protocol, within RFC 2702, entitled “Requirements for Traffic Engineering Over Multi Protocol Label Switching (“MPLS”).” MPLS utilizes a routing approach whereby the normal mode of operation is that the operator of the network explicitly sets up MPLS composite flows on a static basis across the network 100. Each MPLS composite flow also is manually assigned a QoS by the operator.
MPLS provides a simple “core” set of mechanisms which can be applied in several ways to provide a rich functionality. Since MPLS defines an architecture and protocol for encapsulating IP traffic in new routing headers, it involves a much more extensive change to conventional IP networks than Diffserv which is exclusively focused on existing routing-independent IP packet fields. The MPLS approach to indicating IP QoS parameters is different from the approach defined in Diffserv. In particular, the MPLS label is intended to improve efficiency and control of the switch network and allow switches to forward packets using predetermined paths according to, among other things, specified QoS levels.
The disadvantage of this protocol, however, like DiffServ, is that the switch can only identify a small set of “standard” QoS patterns, thereby greatly restricting the future services available to a network 100 that requires a wide variety of QoS types to be used. Furthermore, even though MPLS allows multiple composite flows on multiple routes, there still are restrictions on multiple paths. In addition, micro-flows still must be grouped into composite flows. In particular, like DiffServ and as illustrated in FIG. 1B, MPLS only can group by pre-determined packet classifications. Therefore, like DiffServ, when a path becomes overloaded, there is no way to reject new micro-flows or to split the composite flow into micro-flows and use alternative routes. Instead, MPLS can only drop random packets.
Accordingly, what is needed is a system and method for improving the quality of service in data transmissions by relying upon per micro-flow state information that enables rate and delay variation requirements to be within a certain quantified level of service.